Estimation statistique de la taille des vues

Conventions mathématiques

En informatique, il est important de pouvoir interpréter et appliquer un
algorithme. On exprime souvent les algorithmes en utilisant une notation
mathématique appelée pseudo-code. Elle a l’avantage de ne pas être
spécifique à un langage informatique donné. Elle a l’inconvénient d’être
intimidante, surtout lorsqu’on trouve les notations mathématiques ardues.
(Ne vous en faites pas : il y a peu de pseudo-code dans ce cours !)

En informatique, on utilise toujours le logarithme en base
2 : $\log 8 =3$. On note parfois le logarithme en base 2
avec $\log_2$. Pour calculer le logarithme en base 2 avec
une calculatrice qui n’a pas le logarithme en base 2,
il suffit d’utiliser la formule
$\log_2 x = \log_a x /\log_a 2$. Dans les faits, il suffit
de diviser le logarithme par $\log_a 2$.

On utilise la convention que $x\leftarrow a$
est l’assignation de la valeur $a$ à la variable $x$.

On note $\lfloor x \rfloor$ le plus grand entier plus petit
ou égal à $x$. On note $\lceil x \rceil$ le plus petit entier plus grand
ou égal à $x$. Nous avons que $\lfloor 0.1 \rfloor = 0$
et $\lceil 0.1 \rceil = 1$. Nous avons aussi que $\lfloor 0.9 \rfloor = 0$
et $\lceil 0.9 \rceil = 1$.

La valeur ${k\choose a}$ est le coefficient binomial définit par ${k\choose a}=\frac{k !}{a ! (k-a) !}$ où
$k !$ est la factorielle.
Par exemple, nous avons ${k\choose 1}=k$, ${k\choose 2}=k(k-1)/2$ et ainsi de suite.

Approche statistique

L’estimation de la taille d’une vue à l’aide d’une méthode statistique se fait normalement par échantillonnage, c’est-à-dire que l’on ne retient qu’une partie de nos données. Un algorithme aléatoire sélectionne les données à retenir.

Exemple. Si je sais que chez 1000 hommes choisis aléatoirement, un homme sur quatre a le cancer, je peux conclure que dans une population de 4 millions d’hommes, environ un million d’hommes ont le cancer.

L’avantage de travailler avec un échantillon est que le traitement peut être beaucoup plus rapide et que l’utilisation de la mémoire est généralement minimale.

L’inconvénient majeur de l’échantillonnage est que si l’on sélectionne un échantillon de nos données avant de faire les calculs, il peut être nécessaire de faire une hypothèse concernant la distribution statistique de nos données.

Exemple. Si je sais que chez 1000 hommes choisis aléatoirement, il n’y a que 40 prénoms différents (incluant Daniel, Robert, Richard, etc.), est-ce que je peux conclure que dans une population de 4 millions d’hommes, il y aura proportionnellement 160 mille prénoms différents ?

En pratique, dans les bases de données, un type d’agrégat particulièrement fréquent et difficile à estimer prend la forme d’une requête SQL avec un GROUP BY (« SELECT D1, D2, ..., Dd FROM table GROUP BY D1, D2, ..., Dd »). Pour comprendre pourquoi il est difficile de faire une telle estimation, supposez que vous disposez d’une table où l’une des colonnes est très biaisées, c’est-à-dire qu’elle comporte des valeurs très peu fréquentes et des valeurs qui sont, au contraire, très fréquentes. Par exemple, prenons la colonne « produit » dans une base de données commerciales. Alors qu’une entreprise en ligne peut disposer de millions de produits (c’est le cas notamment de la société Amazon), la plupart des achats peuvent ne porter que sur une centaine ou un millier de produits. Ainsi, une requête de la forme « SELECT produit FROM table GROUP BY produit » peut donner un résultat qui comporte des millions de rangées, alors que si on utilise un échantillon et qu’on y fait la même requête, seulement un petit millier de produits seront sélectionnés.

Il faut donc, d’une certaine manière, pouvoir estimer rapidement le biais des distributions. Heureusement, en pratique, les données sont souvent distribuées de manière assez prévisibles ce qui rend la chose plus facile. Par exemple, Faloutsos et al. [1] ont observé qu’on rencontre souvent des distributions multifractales dans le contexte des grandes bases de données.

Une distribution multifractale est définie comme suit. On suppose qu’il y a $2^k$ valeurs distinctes. L’entier $k$ est l’ordre de la distribution. On choisit une probabilité $p$ ($0 \leq p \leq 1$). La valeur $p$ est le biais de la distribution. Initiallement, on dispose les valeurs distinctes en deux tas de taille égale. Le premier tas reçoit une probabilité de $p$ alors que le second reçoit une probabilité de $1-p$. On procède alors de manière itérative. Le premier tas, celui ayant une probabilité totale de $p$, est divisé en deux tas auxquels ont alloue des probabilités de $p^2$ et $p(1-p)$. Et ainsi de suite.

Exemple. Une distribution multifractale d’ordre 3 ($k=3$) et de biais $0.7$ ($p=0.7$) portera sur $2^3=8$ valeurs distinctes ayant des probabilités de $(1-p)^3=0.027$, $(1-p)^2 p=0.063$, $(1-p)^2 p=0.063$, $(1-p) p^2=0.147$, $(1-p)^2 p=0.063$, $(1-p) p^2=0.147$, $(1-p) p^2=0.147$, $p^3= 0.343$.

Exercice. Expliquez pourquoi la somme des probabilités dans une distribution multifractale doit être égale à un ?

Sur la base de ce type de distribution, Faloutsos et al. propose d’utiliser l’algorithme suivant pour estimer rapidement la taille d’une requête de type "SELECT D1, D2, ..., Dd FROM table GROUP BY D1, D2, ..., Dd". Cet algorithme a la particularité d’estimer tout à la fois le biais de la distribution et la taille de la vue. Il est aussi facile à mettre en oeuvre.

Nous avons une version mise en oeuvre en Java.

Voici le pseudocode :

En entrée : Une table $t$ comportant $N$ rangées

En entrée : Une sélection de colonnes $D_1, D_2, \ldots, D_d$

En entrée : Un ratio d’échantillonnage $0\lt p \lt1$

En sortie : L’estimation de la taille d’une requête GROUP BY sur ces colonnes

– Choisir un échantillon $t’$ comportant $N’=\lfloor pN \rfloor$ rangées
– Calculez le GROUP BY $t’$ sur les colonnes $D_1, D_2, \ldots, D_d$, stockez le résultat dans $g$
– Soit $m_{\textrm{max}}$ le nombre d’occurrences de la rangée
$x_1,\ldots, x_d$ la plus fréquente dans $g$
– Soit $F_0$ le nombre de rangées dans $g$
– Posons $k \leftarrow \lceil\log F_0 \rceil$
– Posons $F \leftarrow 0$
– Tant que $F\lt F_0$ :

• $p\leftarrow (m_\textrm{max}/{N’})^{1/k}$
• $F\leftarrow \sum_{a=0}^k {k\choose a} (1-(p^{k-a}(1-p)^a)^{N’})$ [2]
• $k \leftarrow k+1$

– Posons $p\leftarrow (m_\textrm{max}/N)^{1/k}$
– Valeur retournée : $\sum_{a=0}^k {k\choose a} (1-(p^{k-a}(1-p)^a)^N)$

Nous reviendrons sur cet algorithme dans l’activité d’autoévaluation. Évidemment, cet algorithme n’est qu’un exemple. Il existe plusieurs travaux sur l’estimation statistique des vues. Si vous voulez en savoir plus, consultez les articles suivants :

– P. Haas, J. Naughton, S. Seshadri, et L. Stokes et J. D.Ullman. Sampling-based estimation of the number of distinct values of an attribute. VLDB’95, pages 311–322, 1995.
– P. Dagum, R. Karp, M. Luby, S. Ross, An Optimal Algorithm for Monte Carlo Estimation, SIAM J. Comput., 2000.